package com.hqq.sort.quick;

import com.hqq.sort.Sort;

/**
 * QuickSort
 * 快速排序
 * [思想]:
 * 把一个数组分成两个子数组 将两部分独立的排序
 * 快速排序和归并排序对比:
 * 归并排序是把数组分成两个子数组 分别排序 并将有序的子数组归并以将整个数组排序 [递归发生在处理数组之前]
 * 快速排序是将数组排序的方式是当连个子数组都有序时整个数组就自然有序了  [递归发生在处理数组之后]
 * [优点]:
 * 1.简洁性 内循环用一个递归的索引将数组元素和一个定值比较
 * 2.比较次数小
 * 缺点:切分不平衡时程序会非常低效
 * [改进方法]:
 * 1.切换到插入排序
 * 对于小数组插入排序比快速排序的效率要高
 * 把if(high<=low) return;换成
 * if(hight<=low+M) Insertion.array(a,low,high); return
 * M一般取5-15之间的任意值
 * 2.三取样切分
 * 使用子数组的一小部分元素的中位数来切分数组
 * 3.熵最优的排序
 * 把数组分成三部分 大于小于等于切分元素的数组元素
 * Created by heqianqian on 2017/8/4.
 */
public class QuickSort extends Sort {

    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    /**
     * 三分段快排
     */
    @SuppressWarnings("unchecked")
    public static void sort3Way(Comparable[] a, int low, int high) {
        if (high <= low) {
            return;
        }
        int lt = low, i = low + 1, gt = high;
        Comparable v = a[low];//取比较元素
        while (i <= gt) {//下标小于最大下标
            int cmp = a[i].compareTo(v);
            if (cmp < 0) {
                exchange(a, lt++, i++);
            } else if (cmp > 0) {
                exchange(a, i, gt--);
            } else {
                i++;
            }//a[low..lt-1]<v=a[lt...gt]<a[gt+1..high]成立
        }
        sort(a, low, lt - 1);
        sort(a, gt + 1, high);
    }

    private static void sort(Comparable[] a, int low, int high) {
        if (high <= low) {
            return;
        }
        int j = partition(a, low, high);//切分
        sort(a, low, j - 1);
        sort(a, j + 1, high);
    }

    /**
     * 将数组切分成两个有序的子数组
     * 思想:
     * 先随意的取a[low]作为切分元素，然后从数组的左端开始向右扫描知道找到一个大于等于它的元素,交换他们的位置
     * 如此继续可以保证左指针i的左侧元素都不大于切分元素 右指针j的右侧元素都不小于切分元素
     * 当两个指针相遇时 只需要把切分元素a[low]和左子数组的最右侧元素a[j]交换后返回j
     */
    private static int partition(Comparable[] a, int low, int high) {
        //把数组切分成a[low,i-1],a[i],a[i+1,high]
        int i = low, j = high + 1;
        Comparable v = a[low];//切分元素
        while (true) {
            //扫描左右 检查扫描是否结束并且交换元素
            //扫描左侧
            while (less(a[++i], v)) {
                if (i == high) {
                    break;
                }
            }
            //扫描右侧
            while (less(v, a[--j])) {
                if (j == low) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exchange(a, i, j);
        }
        exchange(a, low, j);
        return j;
    }
}
